/**
 * 
 */
package string;

import java.util.Stack;

/**
 * Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
 *
 * For "(()", the longest valid parentheses substring is "()", which has length = 2.
 *
 * Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4. 
 * 
 * @author xyyi
 *
 */
public class LongestValidParentheses {

	/**
	 * 
	 */
	public LongestValidParentheses() {
		// TODO Auto-generated constructor stub
	}

	public int longestValidParenthesesDP(String s) {
		int n = s.length();
		int[] dp = new int[n + 1];
		int max = 0;
		for (int i = n - 2; i >= 0; i--) {
			if (s.charAt(i) == '(') {
				int j = i + 1 + dp[i + 1];
				if (j < n && s.charAt(j) == ')') {
					dp[i] = 2 + dp[i + 1] + dp[j + 1];
					max = Math.max(max, dp[i]);
				}
			}
		}

		return max;
	}

	/*
	 * （）（（）（）（（） 
	 * 第1次遇到前括号，入栈index是0，然后遇到后括号，现在的长度是 1 - 0 + 1
	 * 第2次遇到前括号，入栈数字是2，当前长度重设为0 第3次遇到前括号，入栈数字是当前长度0.然后后括号，出栈，长度是2+0，
	 * 第4次遇到前括号，入栈数字是当前长度2.然后后括号，出栈，长度是2+2， 第5次遇到前括号，入栈数字是当前长度4，当前长度重设为0
	 * 第6次遇到前括号，入栈数字是当前长度0，遇到后括号，出栈，长度是2.
	 * 如果栈内仍有数字，目前是2，4，则全部出栈，和当前长度2比。取最长为4.rW35
	 */
	public int longestValidParentheses(String s) {
		if (s == null || s.isEmpty()) {
			return 0;
		}

		int max = 0;
		Stack<Integer> stack = new Stack<Integer>();
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if (c == '(') {
				stack.push(i);
			} else if (c == ')') {
				if (!stack.isEmpty() && s.charAt(stack.peek()) == '(') {
					stack.pop();
					int len = stack.isEmpty() ? i + 1 : i - stack.peek();
					max = Math.max(len, max);
				} else {
					stack.push(i);
				}
			}
		}

		return max;
	}

	public int longestValidParentheses2Scan(String s) {
		int result = 0;
		int curMax = 0;
		int counter = 0;

		// forward scan
		for (char c : s.toCharArray()) {
			if (c == '(') {
				counter++;
				curMax++;
			} else if (c == ')') {
				counter--;
				curMax++;
			}

			if (counter < 0) {
				counter = 0;
				curMax = 0;
			} else if (counter == 0) {
				result = Math.max(curMax, result);
			}
		}

		// backward scan
		counter = 0;
		curMax = 0;
		for (char c : s.toCharArray()) {
			if (c == ')') {
				counter++;
				curMax++;
			} else if (c == '(') {
				counter--;
				curMax++;
			}

			if (counter < 0) {
				counter = 0;
				curMax = 0;
			} else if (counter == 0) {
				result = Math.max(result, curMax);
			}
		}

		return result;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		String s = "()((())((";
		LongestValidParentheses lvp = new LongestValidParentheses();
		System.out.printf(
				"longest valid parentheses of %s is %d (expected 4)\n", s,
				lvp.longestValidParentheses2Scan(s));
	}

}
